package com.yun.algorithmproblem.leetcode;

import java.util.*;

public class Leetcode2642 {
    static class Graph {
        private List<int[]>[] graph;

        public Graph(int n, int[][] edges) {
            graph = new List[n];
            for (int i = 0; i < n; i++) {
                graph[i] = new ArrayList<>();
            }
            for (int[] edge : edges) {
                addEdge(edge);
            }
        }

        public void addEdge(int[] edge) {
            graph[edge[0]].add(new int[]{edge[1], edge[2]});
        }

        public int shortestPath(int node1, int node2) {
            PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
            int[] dist = new int[graph.length];
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[node1] = 0;
            heap.offer(new int[]{node1, 0});
            while (!heap.isEmpty()) {
                int[] poll = heap.poll();
                if (poll[0] == node2) {
                    return dist[node2];
                }
                for (int[] nextArr : graph[poll[0]]) {
                    int next=nextArr[0];
                    int cost=nextArr[1];
                    if (dist[poll[0]] + cost < dist[next]) {
                        dist[next] = dist[poll[0]] + cost;
                        heap.offer(new int[]{next, dist[next]});
                    }
                }
            }
            return -1;
        }
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] edges = {{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
        Graph obj = new Graph(n, edges);
        System.out.println(obj.shortestPath(3, 2));
        System.out.println(obj.shortestPath(0, 3));
        obj.addEdge(new int[]{1, 3, 4});
        System.out.println(obj.shortestPath(0, 3));
    }
}
